Funciones recursivas (página 2)

Partes: 1, 2

Formas de definición de las funciones recursivas
Definición usual: Aplicar la definición repetidamente, utilizando una pila de cálculos parciales, hasta que se llegue al resultado
Ejemplo: Para la función de Ackerman,
F(1,1) = F(0,F(1,0)) = F(0,F(0,0)) = F(0,1) = 2

Formas de definición de las funciones recursivas
Forma rigurosa (aunque teórica):
Definir F sobre un primer dominio, D0, donde se puede calcular directamente
Ejemplo: Para la función de Ackerman, D0={(i,x)|i=0}, en cuyo caso f0(i,x)=x+1
Definir F sobre un dominio Dj+1 si su cálculo se puede reducir al de F sobre Dj
Ejemplo: D1=D0?{(i,x) | x=0}; f1(i,x) = …
D2=D1?{(1,1)}; f2(i,x) = …, etc

Formas de definición de las funciones recursivas
Interpretación de la forma anterior: punto fijo de un operador
P(f)(x) = (i=0) ? x+1 : ((x=0) ? f(i-1,1) : f(i-1,f(i,x-1)))
P(f0) = f1
P(f1) = f2
…
F es un punto fijo de P: P(F) = F

EJERCICIOS
[REC 1] Calcular el dominio y los valores de las imágenes de las funciones f y g definidas mediante
f(x,y) = 2.f(y, 2.x)
g(x) = (x < 5) ? f(x, x) : ((x = 5) ? 1 : x*g(x-1))
[REC 2] Calcular el dominio y los valores de las imágenes de la función h definida mediante
h(x, y) = (x = 0) ? 1 : h(x – 1, h(|x – y|, y))

Funciones recursivas: Minimización
Si f(x,y) es una función recursiva, entonces
g(x) = min { y | f(x,y) ? 0 }
define otra función recursiva
Demostración: Definimos
gaux(x, z) = min { y | f(x, z+y) ? 0 }
entonces
gaux(x, z) = (f(x, z) ? 0) ? 0 : 1 + gaux(x, z+1)
g(x) = gaux(x,0)

EJERCICIOS
Suponiendo que la función f(x,y) sea recursiva, demostrar que también lo es la función g(x) cuyo valor es la suma f(x,0) + f(x,1) + … + f(x,n) donde n se elije de manera que los sumandos sean diferentes de 0 y f(x,n+1)=0.

Ejemplo de funciones recursivas: Máquinas de Turing
Dada una máquina de Turing determinista M, la función transita(x, y), donde x e y son estados instantáneos de ejecución de M, que vale “a” si la máquina M lleva la cinta del estado x al y y ? en caso contrario, es recursiva (pero no recursiva primitiva)

Ejemplo de funciones recursivas: Máquinas de Turing
Demostración:
transita(x, y) = esEstado(x) & esEstado(y) &
& ((x=y) ? “a” : transita(aplicaRegla(x), y))
La función aplicaRegla(x) devuelve el resultado de aplicar una regla de transición de M a partir del estado de ejecución x; si no se puede, devuelve x.
EJERCICIO: [MT REC] Demostrar que las funciones esEstado(x) y aplicaRegla(x) son recursivas primitivas.

Ejemplo de funciones recursivas: Máquinas de Turing
Dada una máquina de Turing determinista M, la función ejecuta(x, y), donde x, y??*, que devuelve el estado instantáneo de ejecución de M a partir de y después de |x| transiciones, es recursiva primitiva.
Demostración:
ejecuta(?, y) = Sqº(y)
ejecuta(S?(x), y) =
aplicaRegla(ejecuta(x, y))

Ejemplo de funciones recursivas: Máquinas de Turing
Dada una máquina de Turing determinista M, la función produce(x), que a cada cadena x le hace corresponder el contenido de la cinta cuando M se para a partir de x es recursiva (pero puede no ser recursiva primitiva)
Demostración:
produce(x) =
quitaEstado(ejecuta(x,miny(para(ejecuta(x, y)))))
Observación: miny se puede definir en este caso de forma análoga a como se hace con números.

Forma normal de funciones recursivas
Todas las funciones recursivas se pueden escribir en la forma
f(x) = p(miny(q(x, y)))
donde p y q son funciones recursivas primitivas.
Las funciones p y q se pueden elegir de manera que p simplemente elimine el contenido de la cinta previo a un separador.

Forma normal: programas
La construcción anterior también se puede hacer con programas en lugar de máquinas de Turing: a partir de cualquier programa podemos construir otro equivalente que incorpora un contador y emula al primero paso a paso y cuando el inicial se para sigue ejecutándose sin hacer nada y guardando en una variable booleana fin la información de que el programa emulado ha terminado.

Forma normal: programas
El cálculo del programa inicial se puede realizar buscando el valor mínimo del contador del programa emulador para el cual la variable fin es cierto, y devolviendo la variable que contiene el valor del programa emulado.

Ejemplo de funciones recursivas: Máquinas de Turing
Si una máquina de Turing tiene una definición mediante submáquinas que es recursiva, la función que define sobre cadenas de caracteres es recursiva.
Como consecuencia de lo anterior, las máquinas de Turing definidas recursivamente mediante submáquinas no proporcionan un mecanismo de computación más potente que las máquinas de Turing simples.

Ejemplo de funciones recursivas: Máquinas de Turing
La demostración de la afirmación anterior se basa en la función FM(q, u, x, v), que da el estado final de ejecución (q’, u’, x’, v’) calculado por la máquina a partir del estado q con la palabra uxv sobre la cinta, apuntando a la x. Su definición es
FM(q, u, x, v) = FM(q’, ?234(FN(q, u, x, v)))
donde N es la submáquina correspondiente a la transición. Esto da lugar a una definición recursiva de las funciones FM.
Si la submáquina es indeterminista, se demuestra de manera análoga utilizando conjuntos de estados en lugar de estados.

Qué funciones son recursivas?
Todas las calculables
Es consecuencia de lo anterior
También es consecuencia de la construcción de una máquina universal que emula máquinas de Turing con submáquinas recursivas

Qué funciones son recursivas?
Las que se obtienen a partir de las recursivas primitivas básicas mediante composición, recursión primitiva y minimización
Es consecuencia de lo anterior